闘本 2.2 後ろからK番目を返す
提出
code: txt
import random
class LinkedListNode:
def __init__(self, value, next_node=None, prev_node=None):
self.value = value
self.next = next_node
self.prev = prev_node
def __str__(self):
return str(self.value)
class LinkedList:
def __init__(self, values=None):
self.head = None
self.tail = None
if values is not None:
self.add_multiple(values)
def __iter__(self):
current = self.head
while current:
yield current
current = current.next
def __str__(self):
values = str(x) for x in self
return " -> ".join(values)
def __len__(self):
result = 0
node = self.head
while node:
result += 1
node = node.next
return result
def values(self):
return x.value for x in self
def add(self, value):
if self.head is None:
self.tail = self.head = LinkedListNode(value)
else:
self.tail.next = LinkedListNode(value)
self.tail = self.tail.next
return self.tail
def add_to_beginning(self, value):
if self.head is None:
self.tail = self.head = LinkedListNode(value)
else:
self.head = LinkedListNode(value, self.head)
return self.head
def add_multiple(self, values):
for v in values:
self.add(v)
@classmethod
def generate(cls, k, min_value, max_value):
return cls(random.choices(range(min_value, max_value), k=k))
class DoublyLinkedList(LinkedList):
def add(self, value):
if self.head is None:
self.tail = self.head = LinkedListNode(value)
else:
self.tail.next = LinkedListNode(value, None, self.tail)
self.tail = self.tail.next
return self
def findk(ll, k):
l = len(ll)
count = l - k
current = ll.head
while count:
current = current.next
count -= 1
return current
ll = LinkedList.generate(100, 0, 9)
print(findk(ll, 5))
解答
code: python
import random
class LinkedListNode:
def __init__(self, value, next_node=None, prev_node=None):
self.value = value
self.next = next_node
self.prev = prev_node
def __str__(self):
return str(self.value)
class LinkedList:
def __init__(self, values=None):
self.head = None
self.tail = None
if values is not None:
self.add_multiple(values)
def __iter__(self):
current = self.head
while current:
yield current
current = current.next
def __str__(self):
values = str(x) for x in self
return " -> ".join(values)
def __len__(self):
result = 0
node = self.head
while node:
result += 1
node = node.next
return result
def values(self):
return x.value for x in self
def add(self, value):
if self.head is None:
self.tail = self.head = LinkedListNode(value)
else:
self.tail.next = LinkedListNode(value)
self.tail = self.tail.next
return self.tail
def add_to_beginning(self, value):
if self.head is None:
self.tail = self.head = LinkedListNode(value)
else:
self.head = LinkedListNode(value, self.head)
return self.head
def add_multiple(self, values):
for v in values:
self.add(v)
@classmethod
def generate(cls, k, min_value, max_value):
return cls(random.choices(range(min_value, max_value), k=k))
class DoublyLinkedList(LinkedList):
def add(self, value):
if self.head is None:
self.tail = self.head = LinkedListNode(value)
else:
self.tail.next = LinkedListNode(value, None, self.tail)
self.tail = self.tail.next
return self
def kth_to_last(ll, k):
leader = follower = ll.head
count = 0
while leader:
if count >= k:
follower = follower.next
count += 1
leader = leader.next
return follower
# O(N) space
def kth_last_recursive(ll, k):
head = ll.head
counter = 0
def helper(head, k):
nonlocal counter
if not head:
return None
helper_node = helper(head.next, k)
counter = counter + 1
if counter == k:
return head
return helper_node
return helper(head, k)
test_cases = (
# list, k, expected
((10, 20, 30, 40, 50), 1, 50),
((10, 20, 30, 40, 50), 5, 10),
)
def test_kth_to_last():
for linked_list_values, k, expected in test_cases:
ll = LinkedList(linked_list_values)
assert kth_to_last(ll, k).value == expected
assert kth_last_recursive(ll, k).value == expected
if __name__ == "__main__":
test_kth_to_last()